#include <bits/stdc++.h>

#include "KamaCoder.h"
#include "LeetCode.h"
#include "sort.h"
using namespace std;

// 可到达路径
class KamaCoder98 {
 public:
  vector<vector<int>> result;  // 结果集
  vector<int> path;            // 路径

  // 邻接表、当前节点、终止节点
  void dfs(const vector<list<int>> &graph, int x, int n) {
    if (x == n) {  // 当前节点已经是终止节点了，递归前已经放入了
      result.push_back(path);
      return;
    }
    // 遍历该节点相连的所有节点
    for (int i : graph[x]) {
      path.push_back(i);  // 遍历加到路径节点中
      dfs(graph, i, n);   // 递归进入下一层递归
      path.pop_back();    // 回溯，撤回本节点
    }
    return;
  }

  // 98 路径可到达
  void run98() {
    int n, m;
    cin >> n >> m;
    // 节点编号从1到n，所以申请n+1
    vector<list<int>> graph(n + 1);

    int s, t;
    while (m--) {
      cin >> s >> t;
      // 使用邻接表，表示s->t是相连的
      graph[s].push_back(t);
    }

    path.push_back(1);
    dfs(graph, 1, n);  // 因为寻找的是到n节点路径，所以终止节点是n

    // 输出结果
    if (result.size() == 0)
      cout << -1 << endl;
    else {
      for (const vector<int> pa : result) {
        for (int i = 0; i < pa.size() - 1; i++) {
          cout << pa[i] << " ";
        }
        cout << pa[pa.size() - 1] << endl;
      }
    }
    return;
  }
};

// 岛屿的数量
class KamaCoder99 {
 public:
  int dir[4][2] = {0, -1, 0, 1, -1, 0, 1, 0};  // 上下左右
  // 棋盘格、是否遍历过矩阵、当前遍历格子的坐标
  // 深度搜索
  void dfs(const vector<vector<int>> &grid, vector<vector<bool>> &visited,
           int x, int y) {
    // 循环遍历四个方向
    for (int i = 0; i < 4; i++) {
      int nextx = x + dir[i][0];
      int nexty = y + dir[i][1];
      // 越界检查
      if (nextx < 0 || nexty < 0 || nextx >= grid.size() ||
          nexty >= grid[0].size())
        continue;
      if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
        visited[nextx][nexty] = true;  // 陆地连接，标记为true s
        dfs(grid, visited, nextx, nexty);  // 再递归看看还有没有相连的陆地
      }
    }
  }
  // 广度搜索
  void bfs(const vector<vector<int>> &grid, vector<vector<bool>> &visited,
           int x, int y) {
    // 队列
    queue<pair<int, int>> que;
    que.push({x, y});      // 把起始位置放进去
    visited[x][y] = true;  // 加入队列中，就标记遍历过了
    while (!que.empty()) {
      pair<int, int> cur = que.front();
      que.pop();
      int curx = cur.first;
      int cury = cur.second;
      for (int i = 0; i < 4; i++) {  // 循环遍历四个方向

        int nextx = curx + dir[i][0];
        int nexty = cury + dir[i][1];
        // 越界检查
        if (nextx < 0 || nexty < 0 || nextx >= grid.size() ||
            nexty >= grid[0].size())
          continue;
        if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
          que.push({nextx, nexty});
          visited[nextx][nexty] = true;  // 只要加入队列，就标记遍历过了
        }
      }
    }
  }

  int run99() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    // 输入
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cin >> grid[i][j];
      }
    }
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    int result = 0;

    // 循环遍历棋盘的每一块
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (!visited[i][j] && grid[i][j] == 1) {
          // visited[i][j] = true;
          result++;  // 没有遇到过的陆地
          // dfs(grid, visited, i, j);
          bfs(grid, visited, i, j);
        }
      }
    }
    cout << result << endl;
    return 0;
  }
};

// 岛屿的最大面积
class KamaCoder100 {
 public:
  // 深度搜索
  void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x,
           int y) {
    for (int i = 0; i < 4; i++) {
      int nextx = x + dir[i][0];
      int nexty = y + dir[i][1];
      // 越界检查
      if (nextx < 0 || nexty < 0 || nextx >= grid.size() ||
          nexty >= grid[0].size())
        continue;
      if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
        count++;
        visited[nextx][nexty] = true;
        dfs(grid, visited, nextx, nexty);
      }
    }
  }

  // 广度搜索
  void bfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x,
           int y) {
    queue<pair<int, int>> que;
    que.push({x, y});
    visited[x][y] = true;
    count++;  // 把陆地放到队列中再计数增加
    while (!que.empty()) {
      pair<int, int> cur = que.front();
      que.pop();
      for (int i = 0; i < 4; i++) {
        int nextx = cur.first + dir[i][0];
        int nexty = cur.second + dir[i][1];
        // 越界检查
        if (nextx < 0 || nexty < 0 || nextx >= grid.size() ||
            nexty >= grid[0].size())
          continue;
        if (!visited[nextx][nexty] && grid[nextx][nexty]) {
          visited[nextx][nexty] = true;
          count++;
          que.push({nextx, nexty});
        }
      }
    }
  }

  int run100() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    // 输入
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cin >> grid[i][j];
      }
    }
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int result = 0;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        // 如果该陆地没有遍历过
        if (!visited[i][j] && grid[i][j] == 1) {
          count = 0;  // 每块陆地的第一块土地
          // visited[i][j] =true;
          // dfs(grid, visited,i,j);
          bfs(grid, visited, i, j);
          result = max(result, count);  // 更新最大面积
        }
      }
    }
    cout << result << endl;
    return 0;
  }
  int count;
  int dir[4][2] = {0, -1, 0, 1, -1, 0, 1, 0};  // 上下左右
};

// 孤岛的总面积
class KamaCoder101 {
 public:
  int count;
  int dir[4][2] = {0, -1, 0, 1, -1, 0, 1, 0};  // 上下左右

  void dfs(vector<vector<int>> &grid, int x, int y) {
    // 把当前陆地赋值为海洋
    grid[x][y] = 0;
    count++;
    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
      int nextx = x + dir[i][0];
      int nexty = y + dir[i][1];
      // 越界检查
      if (nextx < 0 || nexty < 0 || nextx >= grid.size() ||
          nexty >= grid[0].size())
        continue;
      if (grid[nextx][nexty] == 1) {
        // 相连是陆地的话，再进行递归
        dfs(grid, nextx, nexty);
      }
    }
  }
  // 广度搜索
  void bfs(vector<vector<int>> &grid, int x, int y) {
    queue<pair<int, int>> que;
    que.push({x, y});
    grid[x][y] = 0;
    count++;
    while (!que.empty()) {
      pair<int, int> cur = que.front();
      que.pop();
      int nextx = cur.first;
      int nexty = cur.second;
      // 越界检查
      if (nextx < 0 || nexty < 0 || nextx >= grid.size() ||
          nexty >= grid[0].size())
        continue;
      if (grid[nextx][nexty] == 1) {
        grid[nextx][nexty] = 0;
        count++;
        que.push({nextx, nexty});
      }
    }
  }

  int run() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cin >> grid[i][j];
      }
    }
    // 与左右边界相连的岛屿
    for (int i = 0; i < n; i++) {
      if (grid[i][0] == 1) dfs(grid, i, 0);
      if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);
    }
    // 与上下边界相连的岛屿
    for (int i = 0; i < m; i++) {
      if (grid[0][i] == 1) dfs(grid, 0, i);
      if (grid[n - 1][i] == 1) dfs(grid, n - 1, i);
    }
    count = 0;
    // 把边界相接壤的岛屿都处理完后，再重新遍历一次网格，即可得到孤岛
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        // if(grid[i][j]==1) dfs(grid,i,j);
        if (grid[i][j] == 1) dfs(grid, i, j);
      }
    }
    cout << count << endl;
    return 0;
  }
};

// 沉没孤岛
/*
class KamaCoder102{
public:
    int count;
    int dir[4][2] = {0, -1, 0, 1, -1, 0, 1, 0}; // 上下左右

    void dfs(vector<vector<int>>&grid ,int x,int y){
        // 把当前陆地赋值为海洋
        grid[x][y] = 2;
        count++;
        // 遍历四个方向
        for(int i=0;i<4;i++){
            int nextx = x +dir[i][0];
            int nexty = y +dir[i][1];
            // 越界检查
            if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size())continue;
            if(grid[nextx][nexty]==1){
                // 相连是陆地的话，再进行递归
                dfs(grid,nextx, nexty);
            }
        }
     }
     // 广度搜索
    void bfs(vector<vector<int>>&grid ,int x,int y){
        queue<pair<int,int>>que;
        que.push({x,y});
        grid[x][y] = 2;
        count++;
        while(!que.empty()){
            pair<int,int>cur = que.front(); que.pop();
            int nextx = cur.first;
            int nexty = cur.second;
            // 越界检查
            if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size())continue;
            if(grid[nextx][nexty]==1){
                grid[nextx][nexty]=2;
                count ++;
                que.push({nextx,nexty});
            }
        }
    }


    int run(){
        int n,m;
        cin>>n>>m;
        vector<vector<int>>grid(n, vector<int>(m));
        for(int i=0; i<n;i++){
            for(int j=0; j<m;j++){
                cin>>grid[i][j];
            }
        }
        // 与左右边界相连的岛屿
        for(int i=0; i<n;i++){
            // if(grid[i][0] == 1) dfs(grid,i,0);
            // if(grid[i][m-1] == 1) dfs(grid,i,m-1);
            if(grid[i][0] == 1) bfs(grid,i,0);
            if(grid[i][m-1] == 1) bfs(grid,i,m-1);
        }
        // 与上下边界相连的岛屿
        for(int i=0; i<m;i++){
            // if(grid[0][i] == 1) dfs(grid,0,i);
            // if(grid[n-1][i] == 1) dfs(grid,n-1,i);
            if(grid[0][i] == 1) bfs(grid,0,i);
            if(grid[n-1][i] == 1) bfs(grid,n-1,i);
        }
        count = 0;
        // 把边界相接壤的岛屿都处理完后，再重新遍历一次网格，即可得到孤岛
        for(int i=0; i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1) grid[i][j] = 0;
                if(grid[i][j]==2) grid[i][j] = 1;
                // if(grid[i][j]==1) dfs(grid,i,j);
            }
        }
        // 输出
        for(int i=0; i<n;i++){
            for(int j=0;j<m;j++){
                cout<<grid[i][j]<<" ";
            }
            cout<<endl;
        }
        return 0;
    }
};
 */

int main111() {
  // KamaCoder98 kamacoder98;
  // kamacoder98.run98();

  // KamaCoder99 kamacoder99;
  // kamacoder99.run99();

  // KamaCoder100 kamacoder100;
  // kamacoder100.run100();

  // KamaCoder101 kamacoder101;
  // kamacoder101.run();

  // KamaCoder102 kamacoder102;
  // kamacoder102.run();

  // KamaCoder103 kamacoder103;
  // kamacoder103.run();

  // KamaCoder104 kamacoder104;
  // kamacoder104.run();

  // KamaCoder110 kamacoder110;
  // kamacoder110.run();

  // KamaCoder105 kamacoder105;
  // kamacoder105.run();

  //  KamaCoder106 kamacoder106;
  //  kamacoder106.run();

  // KamaCoder107 kamacoder107;
  // kamacoder107.run();

  // KamaCoder108 kamacoder108;
  // kamacoder108.run();

  // // 实例化109进行测试
  // KamaCoder109 kamacoder109;
  // kamacoder109.run();

  // 实例化53进行测试
  // KamaCoder53 kamacoder53;
  // kamacoder53.krushkalrun();

  // 实例化117进行测试
  // KamaCoder117 kamacoder117;
  // kamacoder117.run();

  // 实例化47进行测试
  // KamaCoder47 kamacoder47;
  // kamacoder47.run();

  // 实例化94进行测试
  // KamaCoder94 kamacoder94;
  // kamacoder94.run();

  // 实例化95进行测试
  // KamaCoder95 kamacoder95;
  // kamacoder95.run();

  // KamaCoder97 kamacoder97;
  // kamacoder97.run2();

  // KamaCoder126 kamacoder126;
  // kamacoder126.run2();

  // 实例化143进行测试
  // KamaCoder143 kamacoder143;
  // kamacoder143.run();

  // 实例化138进行测试
  // KamaCoder138 kamacoder138;
  // kamacoder138.run();

  // Sort sort;
  // // 分别测试不同排序算法结果
  // vector<int> nums = {3, 2, 1, 5, 6, 4};
  // sort.Insertsort(nums);
  // cout << "Insertsort:";
  // sort.PrintArr(nums);

  // nums = {3, 2, 1, 5, 6, 4};
  // sort.Shellsort(nums);
  // cout << "Shellsort:";
  // sort.PrintArr(nums);

  // nums = {3, 2, 1, 5, 6, 4};
  // sort.Selectionsort(nums);
  // cout << "Selectionsort:";
  // sort.PrintArr(nums);

  // nums = {3, 2, 1, 5, 6, 4};
  // sort.Bubblesort(nums);
  // cout << "Bubblesort:";
  // sort.PrintArr(nums);

  // vector<int> nums = {3, 2, 1, 5, 6, 4};
  // sort.Quicksort(nums, 0, nums.size() - 1);
  // cout << "Quicksort:";
  // sort.PrintArr(nums);

  //
  // LeetCode2787 leetcode2787;
  // cout << leetcode2787.numberOfWays(10, 2) << endl;

  return 0;
}

#include <set>
#include <unordered_set>

#include <bits/stdc++.h>
using namespace std;

#if 0
// 快速排序
// 区间内找出基准值 pivot
int Partition(vector<int>& arr, int left, int right) {
  // 选择左边的元素作为基准值
  int key = arr[left];
  int pivot = left;  // 坑位的索引
  while (left < right) {
    // 右边指针向左移动,直到找到小于等于key的元素
    while (left < right && arr[right] >= key) {
      right--;
    }
    // 交换左右指针指向的元素，并更新坑位
    // swap(arr[pivot], arr[right]);
    arr[pivot] = arr[right];
    pivot = right;  // 更新坑位,可以理解为这个位置的元素为空

    // 左边指针向右移动,直到找到大于key的元素
    while (left < right && arr[left] <= key) {
      left++;
    }
    // 交换左右指针指向的元素，并更新坑位
    // swap(arr[pivot], arr[left]);
    arr[pivot] = arr[left];
    pivot = left;  // 更新坑位,可以理解为这个位置的元素为空
  }
  arr[pivot] = key;  // 基准值放到坑位
  return pivot;      // 返回坑位的索引
}

// 递归调用
void Quicksort(vector<int>& arr, int left, int right) {
  if (left >= right) return;                // 递归终止条件
  int pivot = Partition(arr, left, right);  // 找出基准值
  // [left,pivot-1] [pivot+1,right]
  Quicksort(arr, left, pivot - 1);   // 左边递归
  Quicksort(arr, pivot + 1, right);  // 右边递归
}

// 打印数组
void PrintArr(vector<int>& arr) {
  for (int i = 0; i < arr.size(); i++) {
    cout << arr[i] << " ";  // 输出数组元素
  }
  cout << endl;
}
#endif

#if 0
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end(), greater<int>());
  vector<int> b(n);
  int left = 0, right = n - 1;
  for (int i = 0; i < n; i += 2) {
    //
    if (left == right) {
      b[left] = a[i];
      break;
    }
    b[left] = a[i];
    b[right] = a[i + 1];
    left++;
    right--;
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    int num = (i + 1) * (n - i);
    res += b[i] * num;
  }
  cout << res << endl;
  return 0;
}
#endif